/*
 * Quicksort is a divide and conquer algorithm which relies on a partition operation: 
 * to partition an array, we choose an element, called a pivot, move all smaller elements 
 * before the pivot, and move all greater elements after it. This can be done efficiently 
 * in linear time and in-place. We then recursively sort the lesser and greater sublists.
 * Efficient implementations of quicksort (with in-place partitioning) are typically unstable 
 * sorts and somewhat complex, but are among the fastest sorting algorithms in practice. 
 * Together with its modest O(log n) space usage, this makes quicksort one of the most popular 
 * sorting algorithms, available in many standard libraries. The most complex issue in quicksort 
 * is choosing a good pivot element; consistently poor choices of pivots can result in drastically 
 * slower (O(n2)) performance, but if at each step we choose the median as the pivot then it works 
 * in O(n log n).
 *
 */

#include <iostream>
using namespace std;

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}

void print_array(int* a, int n, char* sep=" "){
	for(int i=0;i<n;i++){
		cout<<a[i]<<sep;
	}
	cout <<endl;
}

int partition(int y[], int f, int l) {
	int up,down,temp;
	int piv = y[f];
	up = f;
	down = l;
	goto partLS;
	do { 
		swap(y[up],y[down]);
partLS:
		while (y[up] <= piv && up < l) {
			up++;
		}
		while (y[down] > piv  && down > f ) {
			down--;
		}
	} while (down > up);
	y[f] = y[down];
	y[down] = piv;
	return down;
}

void quicksort(int x[], int first, int last) {
	int pivIndex = 0;
	if(first < last) {
		pivIndex = partition(x,first, last);
		quicksort(x,first,(pivIndex-1));
		quicksort(x,(pivIndex+1),last);
	}
}


int main(){
	int array[]={20,2,3,9,1,50,10,5,20};
	int n=sizeof(array)/sizeof(int);
	cout<<"before\n";
	print_array(array,n);

	quicksort(array,0,n-1);

	cout<<"after\n";
	print_array(array,n);
}
